package leetcode.秋招.字节跳动.字节研发在线编程;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/7/25 13:31
 * @description：https://www.nowcoder.com/practice/93aacb4a887b46d897b00823f30bfea1?tpId=190&&tqId=35215&rp=1&ru=/activity/oj&qru=/ta/job-code-high-rd/question-ranking
 */
public class NC94LFU缓存结构设计 {
    @Test
    public void test() {
        Solution solution = new Solution();
    }

    public class Solution {
        /**
         * lfu design
         * @param operators int整型二维数组 ops
         * @param k int整型 the k
         * @return int整型一维数组
         */
        public int[] LFU (int[][] operators, int k) {
            // write code here
            LFUCache lfuCache = new LFUCache(k);
            ArrayList<Integer> res = new ArrayList<>();
            for (int[] operator : operators) {
                if (operator[0] == 1) {
                    lfuCache.put(operator[1], operator[2]);
                } else {
                    res.add(lfuCache.get(operator[1]));
                }
            }
            int[] ans = new int[res.size()];
            for (int i = 0; i < res.size(); i++) {
                ans[i] = res.get(i);
            }
            return ans;
        }

        class LFUCache {
            //容量
            int capacity;
            //map
            Map<Integer, Node> map;
            //双向链表
            DoubleList list;

            public LFUCache(int capacity) {
                this.capacity = capacity;
                map = new HashMap<>();
                list = new DoubleList();
            }

            /**
             *  1、已经存在key
             *      -覆盖val，frequency++
             *      -删除链表中的节点，重新加入
             *  2、不存在
             *      -达到了最大容量
             *          删除链表第一个元素，执行插入操作
             *      -未达到
             *          直接插入节点
             * @param key
             * @param val
             */
            public void put(int key, int val) {
                if (map.containsKey(key)) {
                    Node node = map.get(key);
                    list.remove(node);
                    node.val = val;
                    node.frequency++;
                    map.put(key, node);
                    list.add(node);
                } else {
                    Node cur = new Node(key, val, 1);
                    if (list.size >= capacity) {
                        Node node = list.removeFirst();
                        map.remove(node.key);
                    }
                    list.add(cur);
                    map.put(key, cur);
                }
            }

            /**
             * 获取val，frequency++，链表重新赋值
             * @param key
             * @return
             */
            public int get(int key) {
                if (!map.containsKey(key)) return -1;
                Node node = map.get(key);
                list.remove(node);
                node.frequency++;
                list.add(node);
                return node.val;
            }
        }

        //双向链表
        class DoubleList {
            //头尾指针
            Node head, tail;
            //节点数量
            int size;

            public DoubleList() {
                this.head = new Node(-1, -1, -1);
                this.tail = new Node(-1, -1, Integer.MAX_VALUE);
                head.next = tail;
                tail.pre = head;
                size = 0;
            }

            /**
             * 删除节点
             * @param node
             * @return
             */
            private Node remove(Node node) {
                node.pre.next = node.next;
                node.next.pre = node.pre;
                size--;
                return node;
            }

            /**
             * 添加节点，并且维护链表顺序
             *  -频次升序
             *  -相同频次，按操作时间早->晚排序（方便删除）
             * @param node
             */
            private void add(Node node) {
                Node temp = head;
                while (node.frequency >= temp.next.frequency) {
                    temp = temp.next;
                }
                node.next = temp.next;
                temp.next.pre = node;
                temp.next = node;
                node.pre = temp;
                size++;
            }

            /**
             * 删除第一个节点，即调用次数最少，且调用发生最早
             * @return
             */
            private Node removeFirst() {
                Node tar = head.next;
                head.next = tar.next;
                tar.next.pre = head;
                size--;
                return tar;
            }

            /**
             * 展示列表，测试使用
             */
            private void list() {
                Node temp = head.next;
                while (temp != null && temp != tail) {
                    System.out.println(temp);
                    temp = temp.next;
                }
            }
        }

        //Node存放K-V值和当前节点操作的频次
        class Node {
            private int key, val, frequency;
            Node pre, next;

            public Node(int key, int val, int frequency) {
                this.key = key;
                this.val = val;
                this.frequency = frequency;
            }
        }
    }


}
